package Heap;

import java.util.Arrays;

public class Heap {
    public int[] elem;
    public int usedSize;

    public Heap() {
        this.elem = new int[10];
    }
    public void initElem(int[] array) {
        elem= Arrays.copyOf(array,array.length);
        usedSize=array.length;
    }
    //建堆的时间复杂度:O(N)
    //推导:一个满二叉树，第一层最多需要调整h-1次，所以T(N)=2^0*(h-1)+2^1*(h-2)+....+2^(h-2)*1(倒数第二层只会交换一次，因为倒数第一层不会交换)
    //使用错位相减法2T(N)-T(N),得到2^0+2^1+2^2+..+2^(h-1)+2^(h-2)-h = 2^h-1-h  =n-log(n+1) (h高度=logn(n+1)向上取整)
    //logn越来愈大会趋于一个常数，所以向下取整得O(N)
    public void creatHeap() {   //父节点的编号是子结点编号-1/2
        for (int parent = (usedSize-1-1)/2; parent >=0 ; parent--) {   //parent从最后的一个结点开始(usedSize-1表示最后一个结点的编号)
            shiftDown(parent,usedSize);
        }
    }
    //向下调整时间复杂度：树的高度
    private void shiftDown(int parent,int end) {    //end表示数的最大下标+1
       int child=2*parent+1;

        while(child<end) {
            if(child+1<end && elem[child]<elem[child+1]) {               //如果是右子树比左子树大，那么他们的最大值就是右子树
                child++;
            }

            if(elem[child]>elem[parent]) {
                int tmp=elem[child];
                elem[child]=elem[parent];
                elem[parent]=tmp;
                parent=child;           //这两行代码是为了当一棵子树交换完后，下面的子树又需要交换
                child=2*parent+1;
            }else {                     //如果已经满足parent大于child，就不用调了
                break;
            }
        }
    }
    //堆得插入和删除
    //向上调整建堆的时间复杂度0(N*logn)
    public void offer(int val) {
        if(isFull()) {
            //扩容
            elem= Arrays.copyOf(elem,elem.length*2);
        }
        elem[usedSize++]=val;
        //向上调整
        shiftUp(usedSize-1);
    }
    private void shiftUp(int child) {
        int parent=(child-1)/2;
        while(parent>=0) {
            if(elem[child]>elem[parent]) {    //不需要判断左右孩子的大小，因为根一定大
                int tmp=elem[child];
                elem[child]=elem[parent];
                elem[parent]=tmp;
                child=parent;
                parent=(child-1)/2;
            }else {
                break;
            }
        }
    }
    public boolean isFull() {
        return usedSize== elem.length;
    }
    public void pop() {         //删队头元素(只会调整第一个元素查看是否满足大小根堆，其他元素都已经满足要求)
        if(isEmpty()) {
            return;
        }
        int tmp=elem[0];
        elem[0]=elem[usedSize-1];
        elem[usedSize-1]=tmp;
        usedSize--;
        shiftDown(0,usedSize);
    }
    public boolean isEmpty() {
        return usedSize==0;
    }

    //堆排序（(升序使用大根堆，降序使用小跟堆)给定一个数组，对数组本身进行排序）
    //如果使用小根堆，那么只能通过poll堆顶的元素来获取最小的元素，要想获得所有元素，只能放到一个新的数组中
    //时间复杂度:O(N*logn)  空间复杂度:O(1)
    public void heapSort() {
        int end=usedSize-1;
        while(end>0) {       //等于0是就已经有序了，无需交换
            int tmp=elem[0];
            elem[0]=elem[end];
            elem[end]=tmp;
            shiftDown(0,end);
            end--;
        }
    }
}
